﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace P2PFileScheduling
{
    public class BreadthFirstDirectedPaths
    {
        private static int INFINITY = Int32.MaxValue;
        private bool[] marked; // marked[v] = is there an s->v path?
        private int[] edgeTo;  // edgeTo[v] = last edge on shortest s->v path
        private int[] distTo;  // _distTo[v] = length of shortest s->v path
        private int source;
        private int type;
        private Digraph graph;

        // Single source
        public BreadthFirstDirectedPaths(Digraph G, int s, int type)
        {
            marked = new bool[G.V];
            distTo = new int[G.V];
            edgeTo = new int[G.V];
            source = s;
            this.type = type;
            for (int v = 0; v < G.V; v++) distTo[v] = INFINITY;
            graph = G;
            bfs();
        }

        // BFS from single source
        private void bfs()
        {
            Queue<int> q = new Queue<int>();
            marked[source] = true;
            distTo[source] = 0;
            q.Enqueue(source);
            int depth = 0;

            Console.WriteLine("Type: {0}", type);

            while (q.Count > 0)
            {
                int v = q.Dequeue();
                foreach (DirectedEdge e in graph.adjacentTyped(v, type, depth))
                {
                    if (!e.valid) continue;

                    if (v == 1 && e.To.number == 2)
                    {
                        if (e.flow >= e.capacity)
                            Console.WriteLine("Flow: {0}, capacity: {1}", e.flow, e.capacity);
                    }

                    if (e.type == type && !marked[e.To.number] && e.flow < e.capacity)
                    {
                        if (v == 1 && (e.To.number == 2 || e.To.number == 3))
                        {
                            Console.WriteLine("type: {0}, marked[..]: {1}, e.flow < e.capacity: {2} < {3}", type, marked[e.To.number], e.flow, e.capacity);
                        }

                        edgeTo[e.To.number] = v;
                        distTo[e.To.number] = distTo[v] + 1;

                        if (v != 0)
                            marked[e.To.number] = true;

                        q.Enqueue(e.To.number);
                    }
                }

                ++depth;
            }

            for (int i = 0; i < edgeTo.Length; ++i)
                Console.WriteLine("{0}: {1}", i, edgeTo[i]);
        }

        //Marks
        private void bfs(Digraph G)
        {
            Queue<int> q = new Queue<int>();
            marked[G.superSource.number] = true;
            distTo[G.superSource.number] = 0;
            q.Enqueue(G.superSource.number);
            while (q.Count > 0)
            {
                int v = q.Dequeue();
                foreach (DirectedEdge e in G.adj[v])
                {
                    if (e.type == type && !marked[e.to().number] && (e.capacity > e.flow) && !(v==G.superSource.number && e.to().number == G.superSink.number))
                    {
                        edgeTo[e.to().number] = v;
                        distTo[e.to().number] = distTo[v] + 1;
                        marked[e.to().number] = true;
                        q.Enqueue(e.to().number);
                    }
                }
            }
        }

        public List<DirectedEdge> getCut()
        {
            List<int> A = new List<int>();
            List<int> B = new List<int>();
            List<DirectedEdge> cut = new List<DirectedEdge>();
            for (int i = 0; i < graph.V; i++)
            {
                if (marked[i] && i != graph.superSink.number)
                {
                    A.Add(i);
                }
                else
                {
                    B.Add(i);
                }

            }

            foreach (int a in A)
            {
                foreach (int b in B)
                {
                    DirectedEdge edge = graph.getEdge(a, b);
                    if (edge != null && edge.flow>0)
                        cut.Add(edge);

                    edge = graph.getEdge(b, a);
                    if (edge != null && edge.flow > 0)
                        cut.Add(edge);
                }
            }


            return cut;
        }

        // length of shortest path from s (or sources) to v
        public int distanceTo(int v)
        {
            return distTo[v];
        }

        // is there a directed path from s (or sources) to v?
        public bool hasPathTo(int v)
        {
            return marked[v];
        }

        // shortest path from s (or sources) to v; null if no such path
        public Stack<int> pathTo_ints(int v)
        {
            if (!hasPathTo(v))
                return null;

            Stack<int> path = new Stack<int>();
            int x;
            for (x = v; distTo[x] != 0; x = edgeTo[x])
                path.Push(x);
            path.Push(x);
            return path;
        }

        // shortest path from s (or sources) to v; null if no such path
        public List<Vertex> pathTo_vert(int v)
        {
            if (!hasPathTo(v))
                return null;
            
            List<Vertex> path = new List<Vertex>();
            int x;

            for (x = v; distTo[x] != 0; x = edgeTo[x])
                path.Add(graph.sources[x]);
            path.Add(graph.sources[x]);

            return path;
        }

        public List<Vertex> VertexPathTo(int v)
        {
            if (!hasPathTo(v))
                return new List<Vertex>();

            List<Vertex> result = new List<Vertex>();
            result.Add(graph.GetVertex(v));
            int x;

            for (x = v; edgeTo[x] != source; x = edgeTo[x])
                result.Add(graph.GetVertex(edgeTo[x]));

            result.Add(graph.GetVertex(source));
            return result;
        }

        public List<DirectedEdge> EdgePathTo(int v)
        {
            if (!hasPathTo(v))
                return new List<DirectedEdge>();

            List<DirectedEdge> result = new List<DirectedEdge>();
            int x, prev;

            for (x = v; x != source; x = edgeTo[x])
            {
                prev = edgeTo[x];
                result.Insert(0, graph.getEdge(prev, x));
            }

            return result;
        }

        // shortest path from s (or sources) to v; null if no such path
        public List<DirectedEdge> pathTo_edge(int v)
        {
            if (!hasPathTo(v))
                return null;
            
            List<DirectedEdge> path = new List<DirectedEdge>();
            int x;

            for (x = v; distTo[x] != 0; x = edgeTo[x])
            {
                for (int i = 0; i < graph.adj[edgeTo[x]].Count; i++)
                {
                    if (graph.adj[edgeTo[x]][i].To.number == x)
                        path.Add(graph.adj[edgeTo[x]][i]);
                }
            }

            for (int i = 0; i < graph.adj[x].Count; i++)
            {
                if (graph.adj[x][i].to().number == 0)
                    path.Add(graph.adj[edgeTo[x]][i]);
            }
            return path;
        }




    }
}